﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.GeneralizedCoinChange.OnlyQuantityModeling
{ 
    public class MemoizedDynamicCoinChanger : IDynamicCoinChanger
    {
        private readonly IList<int> _values;
        private readonly int _n;
        private readonly IList<double> _weights;

        public MemoizedDynamicCoinChanger(IList<int> values, IList<double> weights = null)
        {
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0, _n).ToAlgoritmiaList();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            var mem = new double[Q + 1];
            var isSetted = new bool[Q + 1];

            Func<int, double> L = null;
            L = q =>
                    {
                        if (q == 0) return 0;
                        for(int i = 0; i < _n; i++)
                        {
                            if (q >= _values[i] && !isSetted[q - _values[i]])
                            {
                                mem[q - _values[i]] = L(q - _values[i]);
                                isSetted[q - _values[i]] = true;
                            }
                        }
                        return
                            Enumerable.Range(0, _n).Where(i => _values[i] <= q).Select(
                                i => mem[q - _values[i]] + _weights[i]).DefaultIfEmpty(double.PositiveInfinity).Min();
                    };
            mem[Q] = L(Q);
            return mem[Q];
        }

        #endregion
    }
}
